package com.fanco.learn_datastruct_leetcode.leetcode;
/**
 * 一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
 * <p>
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * <p>
 * 问总共有多少条不同的路径？
 * <p>
 * input: m = 3, n = 2
 * output: 3
 * @author Fanco
 */
public class Day28 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.uniquePaths(3,2));
    }
    private static class Solution {
        /**
         * 这道题可以通过动态规划的思路来解决
         * 设 f[i][j] 为 从左上角 走到 （i,j）的路径数。
         * @param m
         * @param n
         * @return
         */
        public int uniquePaths(int m, int n) {
            int[][] f = new int[m][n];
            // 对于 在第一行的 所有元素，到达它的路径只有一条。
            for (int i = 0; i < m; i++) {
                f[i][0] = 1;
            }
            // 对于 在第一列的 所有元素，到达它的路径只有一条。
            for (int j = 0; j < n; ++j) {
                f[0][j] = 1;
            }
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
            return f[m-1][n-1];
        }
    }
}
